// java.util.Stack
// 3.1 Describe how you could use a single array to implement three stacks.
 // Approach 1
 // Divide array in 3 equal parts (limited space)
class StackInArray1 {
	int stackSize = 300; 
	int[] buffer = new int[stackSize*3];
	int[] stackPointer = { 0, 0, 0 }; // stack pointer to track top element
	
	void push(int stackNo, int value) {
		int index = stackNo * stackSize + stackPointer[stackNo] +1; 
		stackPointer[stackNo] ++;
		buffer[index] = value; 
	}
	int pop(int stackNo) {
		int index = stackNo*stackSize + stackPointer[stackNo];
		stackPointer[stackNo]--;
		int value = buffer[index];
		buffer[index] = 0;
		return value;
	}
	int peek(int stackNo){ // return top element
		int index = stackNo*stackSize + stackPointer[stackNo];
		return buffer[index];
	}
	
	boolean isEmpty(int stackNo){
		return stackPointer[stackNo] == 0; // in the book, rval is  stackNo * stackSize
	}
} // Approach 1

 // Approach 2
 // stack can grow as long as there is any space in array
 // sequentially allocate space to the stacks and link blocks
class StackInArray2 {
	
	
}


// end of 3.1


class Stack {
	Node top; // see Ch2.
	Node pop(){
		if ( top != null ) {
			Object item = top.data;
			top = top.next;
			return item;
		}
		return null;
	}
	void push( Object item ) {
		Node t = new Node(item);
		t.next = top;
		top = t;
	}
}

// 3.2 push, pop, and min function in O(1) time complexity
public class StackWithMin extends Stack<NodeWithMin> {
	public void push(int value) {
		int newMin = Math.min(value, min());
		super.push(new NodeWithMin(value, newMin));
	}
	
	public int pop(){
		super.pop();
	}
	
	public int min() {
		if(this.isEmpty())
	}
	
}

class NodeWithMin {
	public int value;
	public int min;
	public NodeWithMin(int value, int min) {
		this.value = value;
		this.min = min;
	}
} // end of 3.2

// 3.5
